package my.ks;

import java.util.Arrays;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;

/**
 * 贪心 - 0-1背包问题: 在保证总重量不超过最大承重的前提下，将哪些物品装入背包，使得背包中物品的总价值最大？
 * 注意: 每个物品只有一件，也就是每个物品只能选0件或者1件，所以称为0-1背包问题
 *
 * @author AJun
 * @date 2020/11/25
 */
public class Knapsack {

    /**
     * 背包最大承重
     */
    static int capacity = 150;

    /**
     * 物品，重量为 Wi，价值为 Vi
     */
    static Article[] articles = new Article[]{
        new Article(35, 10), new Article(30, 40),
        new Article(60, 30), new Article(50, 50),
        new Article(40, 35), new Article(10, 40),
        new Article(25, 30)
    };

    public static void main(String[] args) {
        select("重量主导", Comparator.comparingInt(a -> a.weight));
        select("价值主导", (a1, a2) -> a2.value - a1.value);
        select("价值密度主导", (a1, a2) -> Double.compare(a2.valueDensity, a1.valueDensity));
    }

    static void select(String title, Comparator<Article> cmp) {
        Arrays.sort(articles, cmp);

        // 选择的物品的总重量
        int weight = 0;
        // 选择的物品的总价值
        int value = 0;
        // 选择的物品
        List<Article> selectedArticles = new LinkedList<>();
        for (int i = 0; i < articles.length && weight < capacity; i++) {
            int newWeight = weight + articles[i].weight;
            if (newWeight <= capacity) {
                weight = newWeight;
                value += articles[i].value;
                selectedArticles.add(articles[i]);
            }
        }

        System.out.println("[" + title + "]");
        System.out.println("总价值：" + value);
        selectedArticles.forEach(System.out::println);
        System.out.println("-----------------------------");
    }

}
